/* Zach Smith
 *
 * Project 1: Sort Algorithm Comparison
 *
 * QuickSort.java
 *
 * Original code found in "Data Abstraction & Problem Soving with Java"
 * 2005., Carrano, F., Prichard, J.; pg. 498
 *
 */

public class QuickSort
{
	private static void ChoosePivot(int[] myArray, int first, int last)
	{
                /***variable declaration***/
		int mid = (last + first)/2; //finds midpoint of array
		int temp;  
                
                /***Find median of first, middle, and last elements of array***/
		if ((myArray[first] > myArray[last] && myArray[first] < myArray[mid])
			|| myArray[first] < myArray[last] && myArray[first] > myArray[mid])
		{
		}
		else if ((myArray[last] > myArray[first] && myArray[last] < myArray[mid])
			|| myArray[last] < myArray[first] && myArray[last] > myArray[mid])
		{
			temp = myArray[last];
			myArray[last] = myArray[first];
			myArray[first] = temp;
		}
		else
		{
			temp = myArray[mid];
			myArray[mid] = myArray[first];
			myArray[first] = temp;
		}
	}

	private static int Partition(int[] myArray, int first, int last)
	{
		int temp;

		ChoosePivot(myArray, first, last);
		int pivot = myArray[first];

		int lastS1 = first;

                /***cycles through unknown elements***/
		for (int firstUnknown = first + 1; firstUnknown <= last; ++firstUnknown)
		{
                        /***decides if unknown is less than pivot***/
			if(myArray[firstUnknown] < pivot)
			{
				++lastS1;
				temp = myArray[firstUnknown];
				myArray[firstUnknown] = myArray[lastS1];
				myArray[lastS1] = temp;
			}
		}
                
                /***switch elements***/
		temp = myArray[first];
		myArray[first] = myArray[lastS1];
		myArray[lastS1] = temp;
		return lastS1;
	}

	public static void QuickSort(int[] myArray, int first, int last)
	{
		int pivotIndex;

                /***runs quicksort algorithm***/
		if (first < last)
		{
			pivotIndex = Partition(myArray, first, last);

			QuickSort(myArray, first, pivotIndex-1);
			QuickSort(myArray, pivotIndex+1, last);
		}
	}
}